package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 919. 完全二叉树插入器
 * @author feizns
 * @since 2020/3/14
 */
public class CBTInserter {

    TreeNode root;

    Queue<TreeNode> queue = new LinkedList<>();

    public CBTInserter(TreeNode root) {
        this.root = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while ( !queue.isEmpty() ) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if ( node.left == null )
                    this.queue.add(node);
                else
                    queue.add(node.left);

                if ( node.right == null )
                    this.queue.add(node);
                else
                    queue.add(node.right);
            }
        }
    }

    public int insert(int v) {
        TreeNode pop = queue.remove();
        TreeNode node = new TreeNode(v);
        if ( pop.left == null )
            pop.left = node;
        else
            pop.right = node;
        queue.add(node);
        queue.add(node);
        return pop.val;
    }

    public TreeNode get_root() {
        return root;
    }

}
